#include <bits/stdc++.h>
#include <cstring>
using namespace std;

//dp
// class Solution {
// public:
//     int longestValidParentheses(string s) {
//         int len = s.length();
//         int dp[len+1];    //dp[i+1]表示包含s[i]的最长有效括号串长度
//         memset(dp, 0, sizeof(dp));
//         int ans = 0;
//         for(int i=0; i<len; ++i){
//             int t = i+1;
//             if(s[i]=='(') dp[t] = 0;
//             else {
//                 if(i>0 && s[i-1]=='(') dp[t] = dp[t-2] + 2;
//                 else if(i>0 && i-dp[t-1]>0 && s[i-1] == ')' && s[i-dp[t-1]-1]=='(')
//                     dp[t] = dp[t-1] + dp[i-dp[t-1]-1] + 2;
//             }
//             ans = max(ans, dp[t]);
//         }
//         return ans;
//     }
// };

//stack
// class Solution {
// public:
//     int longestValidParentheses(string s) {
//         int ans = 0;
//         stack<int> stk; stk.push(-1);   //设置')'作为基底
//         int len = s.length();
//         for(int i=0; i<len; ++i){
//             if(s[i] == '(') stk.push(i);
//             else {
//                 stk.pop();
//                 if(stk.empty()){
//                     stk.push(i);    //最新的')'作为基底(隔板作用)
//                 }
//                 else {
//                     ans = max(ans, i-stk.top());
//                 }
//             }
//         }
//         return ans;
//     }
// };

//贪心:因为如果right>left，则无论window左端右移还是右端右移，都不可能使window中的串变得合法
//left和right计数器
class Solution {
public:
    int longestValidParentheses(string s) {
        int left=0, right=0;
        int ans = 0;
        for(auto& chr: s){
            if(chr=='(') ++left;
            else ++right;
            if(right > left) left=right = 0;
            else if(right == left) ans = max(ans, right+left);
            //left > right 不考虑， 反向可解决
        }

        int len = s.length();
        left = right = 0;
        for(int i=len-1; i>-1; --i){
            if(s[i] == ')') ++right;
            else ++left;
            if(left > right) left = right = 0;
            else if(left == right) ans = max(ans, left + right);
        }
        return ans;
    }
};
int main(){
    Solution solution;
    solution.longestValidParentheses("(()");
}